package Algorithm.prim;

import graph.Graph;

import java.util.Arrays;

//prim算法，解决连通图的最小生成树
public class PrimAlgorithm {
	public static void main(String[] args) {
		char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//设置邻接矩阵,用 1000 表示两点距离很大，不连通
		int[][] weight = {{1000, 5, 7, 1000, 1000, 1000, 2},
				{5, 1000, 1000, 9, 1000, 1000, 3},
				{7, 1000, 1000, 1000, 8, 1000, 1000},
				{1000, 9, 1000, 1000, 1000, 4, 1000},
				{1000, 1000, 8, 1000, 1000, 5, 4},
				{1000, 1000, 1000, 4, 5, 1000, 6},
				{2, 3, 1000, 1000, 4, 6, 1000}};


//        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//        //设置邻接矩阵,用 1000 表示两点距离无穷大，不连通；自己到自己距离为0
//        int[][] weight = {{1000, 12, 1000, 1000, 1000, 16, 14},
//                          {12, 1000, 10, 1000, 1000, 7, 1000},
//                          {1000, 10, 1000, 3, 5, 6, 1000},
//                          {1000, 1000, 3, 1000, 4, 1000, 1000},
//                          {1000, 1000, 5, 4, 1000, 2, 8},
//                          {16, 7, 6, 1000, 2, 1000, 9},
//                          {14, 1000, 1000, 1000, 8, 9, 1000}};


		int vertex = data.length;
		//创建一个 图对象
		MyGraph myGraph = new MyGraph(vertex);
		//创建一个 最小生成树对象
		MinTree minTree = new MinTree();
		minTree.createGraph(myGraph, vertex, data, weight);
		minTree.showGraph(myGraph);


		minTree.prim(myGraph, 0);

	}
}

//创建最小生成树
class MinTree {
	/**
	 * 创建图的邻接矩阵
	 *
	 * @param graph  图对象
	 * @param vertex 图中顶点个数
	 * @param data   各个顶点的值
	 * @param weight 图的邻接矩阵
	 */
	public void createGraph(MyGraph graph, int vertex,
	                        char data[], int[][] weight) {
		//遍历所有顶点
		for (int i = 0; i < vertex; i++) {
			//给每个顶点赋值
			graph.data[i] = data[i];
			//初始化邻接矩阵
			for (int j = 0; j < vertex; j++) {
				graph.weight[i][j] = weight[i][j];
			}
		}
	}

	//显示图对应的邻接矩阵
	public void showGraph(MyGraph graph) {
		System.out.println("邻接矩阵：");
		for (int[] link : graph.weight) {
			System.out.println(Arrays.toString(link));
		}
		System.out.println();
	}

	// prim 算法，得到最小生成树=========================

	/**
	 * @param graph 图对象
	 * @param v     标识从图的第几个顶点开始生成（顶点对应的下标）
	 */
	public void prim(MyGraph graph, int v) {
		// 1. 表示 下标对应的顶点是否被访问过
		int[] visited = new int[graph.vertex];
		// 2. 把当前顶点标记为已访问
		visited[v] = 1;

		// 用 h1 和 h2 来记录两个顶点的下标
		int h1 = -1;
		int h2 = -1;
		//初始化最小距离，先初始化为最大值
		int minWeight = 1000;
		//记录距离总和
		int sumOfWeight = 0;

		System.out.println("prim算法得到的最小生成树为：");
		// 因为有 vertex 个顶点，vertex 条边，所以 k 从 1 开始遍历
		for (int k = 1; k < graph.vertex; k++) {
			// 3. 找到已经生成的树的一个顶点，并且遍历它还未被访问过的相邻顶点，找到一个距离最短的

			//遍历已经访问过的顶点
			for (int i = 0; i < graph.vertex; i++) {
				//遍历未访问过的顶点
				for (int j = 0; j < graph.vertex; j++) {
					// 第 i 个以访问过，第 j 个未被访问过，i -> j 的距离小于之前保存的最短距离
					if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						//替换 最短距离
						minWeight = graph.weight[i][j];
						//记录顶点 i 和 j 的下标
						h1 = i;
						h2 = j;
					}
				}
			}
			sumOfWeight += minWeight;
			//找到距离最短的边
			System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">,权值：" + minWeight);
			// 4。 把找到的节点，标记为以访问
			visited[h2] = 1;
			//  重置最短距离
			minWeight = 1000;
		}
		System.out.println("最短距离总和为：" + sumOfWeight);
	}
	//=================================================
}

//创建图
class MyGraph {
	int vertex;//图中节点个数
	char[] data;//存放数据
	int[][] weight;//邻接矩阵

	public MyGraph(int vertex) {
		this.vertex = vertex;
		data = new char[vertex];
		weight = new int[vertex][vertex];
	}
}
